//中缀表达式转后缀表达式(机算算法)
/*
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况：

1. 遇到操作数。直接加入后缀表达式。
2. 遇到界限符。遇到 ‘ ( ’ 直接入栈；遇到 ‘ ) ’ 则依次弹出栈内运算符并加入后缀表达式，直到弹出 ‘ ( ’ 为止。注意：‘ ( ’ 不加入后缀表达式。
3. 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到 ‘ ( ’ 或栈空则停止。之后再把当前运算符入栈。

按上述方法处理完所有字符后，将栈中运算符依次弹出，并加入后缀表达式。
*/

#include <iostream>
#include <string>

using namespace std;

string infixToSuffix(string s)
{
    string ans; //后缀表达式字符串

    char OS[10000]; // Opreator stack：用于保存暂时还不能确定运算顺序的运算符
    int size = 0;

    for (int i = 0; i < s.length(); i++)
    {
        switch (s[i])
        {
        case '+':
        case '-':
            while (OS[size - 1] != '(' && size != 0)
            {
                ans.push_back(OS[size - 1]);
                size--;
            }
            OS[size++] = s[i];
            break;

        case '*':
        case '/':
            while (size != 0 && OS[size - 1] != '+' && OS[size - 1] != '-' && OS[size - 1] != '(')
            {
                ans.push_back(OS[size - 1]);
                size--;
            }
            OS[size++] = s[i];
            break;
        case '(':
            OS[size++] = s[i];
            break;
        case ')':
            while (OS[size - 1] != '(')
            {
                ans.push_back(OS[size - 1]);
                size--;
            }
            size--;
            break;
        default:
            ans.push_back(s[i]);
            break;
        }
    }
    while (OS[size - 1] != '(' && size != 0)
    {
        ans.push_back(OS[size - 1]);
        size--;
    }
    return ans;
}

int main()
{
    string s;
    cout << "Infix:  ";
    cin >> s;
    cout << "Suffix: " << infixToSuffix(s);
    return 0;
}